home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 311_01 / db_idx.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-04-21  |  30.3 KB  |  1,004 lines
  1. /****************************************************************************/
  2. /*                                                                          */
  3. /*                                                                          */
  4. /*      db_idx.c  v1.3  (c) 1987-1990  Ken Harris                           */
  5. /*                                                                          */
  6. /*                                                                          */
  7. /****************************************************************************/
  8. /*                                                                          */
  9. /*      This software is made available on an AS-IS basis. Unrestricted     */
  10. /*      use is granted provided that the copyright notice remains intact.   */
  11. /*      The author makes no warranties expressed or implied.                */
  12. /*                                                                          */
  13. /****************************************************************************/
  14.  
  15. #include "dblib.h"
  16.  
  17.  
  18. /*
  19.  *      db_add_idx  -  Add record to an index file
  20.  */
  21.  
  22. void db_add_idx(df, user_data)
  23.  DATA_FILE df;
  24.  char *user_data;
  25. {
  26.         FILE_HDR    fh;
  27.         INDEX_HDR ihdr;
  28.         INDEX_REC irec;
  29.         BUFFER     buf;
  30.         char     *rbuf, *src, *dst;
  31.         ushort     rec;
  32.         int        cnt;
  33.  
  34.         db_error     = 0;
  35.  
  36.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  37.         buf  = df->df_buf;
  38.         ihdr = (INDEX_HDR) buf->buf_data;
  39.         rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  40.  
  41.         if (!fh->fh_root_ptr)
  42.         {       db_get_next_avail(df, buf);
  43.                 if (db_error) return;
  44.         }
  45.         else
  46.         {       db_find_insert_idx(df, user_data, fh->fh_key_size);
  47.                 if (db_match_blk)
  48.                         if (!(fh->fh_file_stat & DB_DUP_ALLOWED))
  49.                         {       db_error = DB_DUP_NOT_ALLOWED;
  50.                                 return;
  51.                         }
  52.         }
  53.                  
  54.         ihdr->idx_rec_cnt++;
  55.         rec = buf->buf_rec_inx;
  56.  
  57.         db_add_blk = buf->buf_cur_blk;
  58.         db_add_rec = buf->buf_rec_inx;
  59.  
  60.         if (rec <= ihdr->idx_rec_cnt)
  61.         {       src = rbuf + (rec - 1) * fh->fh_rec_size;
  62.                 dst = src + fh->fh_rec_size;
  63.                 cnt = (ihdr->idx_rec_cnt - rec + 1) * fh->fh_rec_size;
  64.                 memcpy(dst, src, cnt);
  65.         }                             
  66.         
  67.         irec = (INDEX_REC) src;
  68.         irec->idx_idx_ptr = 0;
  69.         dst = (char *) irec + fh->fh_ctl_size;
  70.         memcpy(dst, user_data, fh->fh_data_size);
  71.  
  72.         fh->fh_rec_cnt++;
  73.  
  74.         db_split_blk_idx(df);
  75.         if (db_error) return;
  76.  
  77.         db_put_blk(df, df->df_fhdr);
  78. }
  79.       
  80. /*
  81.  *      db_find_insert_idx  -  Find Insert Point in an index File
  82.  */
  83.  
  84. void db_find_insert_idx(df, key, key_size)
  85.  DATA_FILE df;
  86.  char *key;                         
  87.  int   key_size;
  88. {
  89.         FILE_HDR    fh;
  90.         INDEX_HDR ihdr;
  91.         INDEX_REC irec;
  92.         BUFFER     buf;
  93.         char     *rbuf, *ikey;
  94.         ulong      blk;
  95.         ushort     rec;
  96.         int          x;
  97.                        
  98.  
  99.         db_error     = 0;
  100.         db_match_blk = 0;
  101.         db_match_rec = 0;
  102.  
  103.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  104.         buf  = df->df_buf;
  105.         ihdr = (INDEX_HDR) buf->buf_data;
  106.         blk  = fh->fh_root_ptr;
  107.  
  108.         if (!key_size) key_size = fh->fh_key_size;
  109.  
  110.         while (blk)
  111.         {       db_get_blk(df, blk, buf);
  112.                 if (db_error) return;
  113.  
  114.                 rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  115.  
  116.                 for (rec=1; rec <= ihdr->idx_rec_cnt; rec++)
  117.                 {       irec = (INDEX_REC) rbuf;
  118.                         ikey = rbuf + fh->fh_ctl_size;
  119.  
  120.                         x = memcmp(key, ikey, key_size);
  121.         
  122.                         if (x == 0)
  123.                         {       db_match_blk = blk;
  124.                                 db_match_rec = rec;
  125.                                 blk = irec->idx_idx_ptr;
  126.                                 break;
  127.                         }
  128.  
  129.                         if (x < 0)
  130.                         {       blk = irec->idx_idx_ptr;
  131.                                 break;
  132.                         }
  133.  
  134.                         rbuf += fh->fh_rec_size;
  135.  
  136.                         if (rec == ihdr->idx_rec_cnt)
  137.                         {       irec = (INDEX_REC) rbuf;
  138.                                 blk  = irec->idx_idx_ptr;
  139.                         }
  140.                 }        
  141.         }
  142.         buf->buf_rec_inx = rec;
  143. }
  144.  
  145. /*
  146.  *      db_split_blk_idx  -  Check for a block split
  147.  */
  148.  
  149. void db_split_blk_idx(df)
  150.  DATA_FILE df;
  151. {
  152.         FILE_HDR   fh;
  153.         BUFFER     buf,  tmp,  aux;
  154.         INDEX_HDR ihdr,  thdr, ahdr;
  155.         INDEX_REC  idx;
  156.         char     *hold, *rbuf, *src,  *dst;
  157.         ushort     cnt,  cnt1,  cnt2;
  158.         ushort     rec,  left, right;
  159.  
  160.         db_error = 0;
  161.  
  162.         fh  = (FILE_HDR) df->df_fhdr->buf_data;
  163.         buf = df->df_buf;
  164.         tmp = df->df_tmp;
  165.  
  166.         ihdr = (INDEX_HDR) buf->buf_data;
  167.  
  168.         if (ihdr->idx_rec_cnt <= fh->fh_recs_per_blk)
  169.         {       db_put_blk(df, buf);
  170.                 return;
  171.         }
  172.  
  173.         buf        = df->df_tmp;
  174.         tmp        = df->df_buf;
  175.         df->df_buf = buf;
  176.         df->df_tmp = tmp;
  177.         aux        = df->df_aux;
  178.  
  179.         db_get_next_avail(df, buf);
  180.         if (db_error) return;
  181.  
  182.         ihdr = (INDEX_HDR) buf->buf_data;
  183.         thdr = (INDEX_HDR) tmp->buf_data;
  184.         ahdr = (INDEX_HDR) aux->buf_data;
  185.  
  186.         left   = tmp->buf_cur_blk;
  187.         right  = buf->buf_cur_blk;
  188.  
  189.         cnt1 = thdr->idx_rec_cnt / 2;
  190.         cnt2 = thdr->idx_rec_cnt - (cnt1 + 1);
  191.  
  192.         ihdr->idx_parent  = thdr->idx_parent;
  193.         ihdr->idx_rec_cnt = cnt2;         
  194.  
  195.         src = tmp->buf_data + sizeof(struct db_index_hdr)
  196.                                                 + (cnt1 + 1) * fh->fh_rec_size;
  197.         dst = buf->buf_data + sizeof(struct db_index_hdr);
  198.         cnt = (cnt2 + 1) * fh->fh_rec_size;
  199.         memcpy(dst, src, cnt);
  200.  
  201.         db_put_blk(df, buf);
  202.         if (db_error) return;
  203.  
  204.         if (db_add_blk == tmp->buf_cur_blk)
  205.                 if (db_add_rec > cnt1 + 1)
  206.                 {       db_add_blk  =  buf->buf_cur_blk;
  207.                         db_add_rec -= cnt1 + 1;         
  208.                 }
  209.  
  210.         rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  211.         if (!thdr->idx_parent)
  212.         {       if (tmp->buf_cur_blk != fh->fh_root_ptr)
  213.                 {       db_error = DB_INVALID_INDEX;
  214.                         return;
  215.                 }
  216.                 db_get_next_avail(df, buf);
  217.                 thdr->idx_parent = buf->buf_cur_blk;
  218.                 fh->fh_root_ptr  = buf->buf_cur_blk;
  219.                 idx              = (INDEX_REC) rbuf;
  220.                 rec              = 1;
  221.         }
  222.         else
  223.         {       db_get_blk(df, (long)thdr->idx_parent, buf);
  224.                 if (db_error) return;
  225.  
  226.                 for (rec=1; rec <= ihdr->idx_rec_cnt+1; rec++)
  227.                 {       idx = (INDEX_REC) rbuf;
  228.  
  229.                         if (idx->idx_idx_ptr == left)
  230.                                 break;
  231.  
  232.                         rbuf += fh->fh_rec_size;
  233.                 }
  234.  
  235.                 if (idx->idx_idx_ptr != left)
  236.                 {       db_error = DB_INVALID_INDEX;
  237.                         return;
  238.                 }
  239.         }
  240.  
  241.         idx->idx_idx_ptr = right;
  242.  
  243.         if (db_add_blk == tmp->buf_cur_blk)
  244.                 if (db_add_rec == cnt1 + 1)
  245.                 {       db_add_blk =  buf->buf_cur_blk;
  246.                         db_add_rec =  rec;
  247.                 }
  248.  
  249.         src = rbuf;
  250.         dst = rbuf + fh->fh_rec_size;
  251.         cnt = ((ihdr->idx_rec_cnt + 1) - rec + 1) * fh->fh_rec_size;
  252.         memcpy(dst, src, cnt);
  253.  
  254.         src = tmp->buf_data + sizeof(struct db_index_hdr)
  255.                                          + cnt1 * fh->fh_rec_size;
  256.         dst = rbuf;
  257.         cnt = fh->fh_rec_size;
  258.         memcpy(dst, src, cnt);
  259.  
  260.         idx->idx_idx_ptr = left;
  261.         ihdr->idx_rec_cnt++;
  262.  
  263.         thdr->idx_rec_cnt = cnt1;
  264.         db_put_blk(df, tmp);
  265.         if (db_error) return;
  266.  
  267.         db_get_blk(df, (long) right, tmp);
  268.         if (db_error) return;
  269.  
  270.         if (thdr->idx_parent != buf->buf_cur_blk)
  271.         {       thdr->idx_parent = buf->buf_cur_blk;
  272.                 db_put_blk(df, tmp);
  273.                 if (db_error) return;
  274.         }
  275.  
  276.         rbuf = tmp->buf_data + sizeof(struct db_index_hdr);
  277.         for (cnt=1; cnt <= thdr->idx_rec_cnt + 1; cnt++)
  278.         {       idx = (INDEX_REC) rbuf;
  279.  
  280.                 if (idx->idx_idx_ptr)
  281.                 {       db_get_blk(df, (long)idx->idx_idx_ptr, aux);
  282.                         if (db_error) return;
  283.  
  284.                         ahdr->idx_parent = tmp->buf_cur_blk;
  285.                         db_put_blk(df, aux);
  286.                         if (db_error) return;
  287.                 }
  288.  
  289.                 rbuf += fh->fh_rec_size;
  290.         }
  291.  
  292.         db_split_blk_idx(df);
  293. }
  294.  
  295. /*
  296.  *      db_read_first_idx  -  Read First Record in an Index File
  297.  */
  298.  
  299. void db_read_first_idx(df, blk, user_data)                           
  300.  DATA_FILE df;
  301.  int blk;
  302.  char *user_data;
  303. {
  304.         FILE_HDR    fh;
  305.         BUFFER     buf;
  306.         INDEX_HDR ihdr;
  307.         INDEX_REC  idx;
  308.         char      *src;
  309.  
  310.                     
  311.         db_error = 0;
  312.  
  313.         if (!blk)
  314.         {       db_error = DB_END_OF_FILE;
  315.                 return;
  316.         }
  317.  
  318.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  319.         buf  = df->df_buf;
  320.         ihdr = (INDEX_HDR)  buf->buf_data;
  321.         idx  = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr));
  322.  
  323.         while (blk)
  324.         {       db_get_blk(df, (long) blk, buf);
  325.                 if (db_error) return;
  326.          
  327.  
  328.                 if (!ihdr->idx_rec_cnt)
  329.                 {       db_error = DB_INVALID_INDEX;
  330.                         return;
  331.                 }
  332.  
  333.                 blk = idx->idx_idx_ptr;
  334.         }                              
  335.  
  336.         src = buf->buf_data + sizeof(struct db_index_hdr) + fh->fh_ctl_size;
  337.         buf->buf_rec_inx = 1;
  338.         memcpy(user_data, src, fh->fh_data_size);
  339. }
  340.  
  341. /*
  342.  *      db_read_next_idx  -  Read Next Record in an Index File
  343.  */
  344.  
  345. void db_read_next_idx(df, user_data)
  346.  DATA_FILE df;
  347.  char *user_data;
  348. {
  349.         FILE_HDR    fh;
  350.         BUFFER     buf;
  351.         INDEX_HDR ihdr;
  352.         INDEX_REC  idx;
  353.         char      *src;
  354.  
  355.                     
  356.         db_error = 0;
  357.  
  358.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  359.         buf  = df->df_buf;
  360.         ihdr = (INDEX_HDR)  buf->buf_data;
  361.                                                
  362.         db_get_blk(df, df->df_prev_blk, buf);
  363.         if (db_error) return;
  364.  
  365.         buf->buf_rec_inx = df->df_prev_rec;
  366.  
  367.         if (buf->buf_rec_inx > ihdr->idx_rec_cnt)
  368.         {       while (buf->buf_rec_inx > ihdr->idx_rec_cnt)
  369.                 {       db_get_parent_idx(df);
  370.                         if (db_error) return;
  371.                 }
  372.  
  373.                 src = buf->buf_data + sizeof(struct db_index_hdr)
  374.                     + (buf->buf_rec_inx - 1) * fh->fh_rec_size
  375.                     + fh->fh_ctl_size;
  376.  
  377.                 memcpy(user_data, src, fh->fh_data_size);
  378.                 return;
  379.         }
  380.  
  381.         buf->buf_rec_inx++;
  382.  
  383.         idx = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr)
  384.             + (buf->buf_rec_inx - 1) * fh->fh_rec_size);
  385.  
  386.         if (idx->idx_idx_ptr)
  387.         {       db_read_first_idx(df, idx->idx_idx_ptr, user_data);
  388.                 return;
  389.         }
  390.  
  391.         if (buf->buf_rec_inx > ihdr->idx_rec_cnt)
  392.         {       df->df_prev_rec = buf->buf_rec_inx;
  393.                 db_read_next_idx(df, user_data);
  394.                 return;
  395.         }
  396.  
  397.         src = ((char *) idx) + fh->fh_ctl_size;
  398.         memcpy(user_data, src, fh->fh_data_size);
  399. }
  400.  
  401. /*
  402.  *    db_read_last_idx  -  Read Last Record in an Index File
  403.  */
  404.  
  405. void db_read_last_idx(df, blk, user_data)
  406.  DATA_FILE df;
  407.  int blk;
  408.  char *user_data;
  409. {
  410.         FILE_HDR    fh;
  411.         BUFFER     buf;
  412.         INDEX_HDR ihdr;
  413.         INDEX_REC  idx;
  414.         char      *src;
  415.  
  416.                     
  417.         db_error = 0;
  418.  
  419.         if (!blk)
  420.         {       db_error = DB_END_OF_FILE;
  421.                 return;
  422.         }
  423.  
  424.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  425.         buf  = df->df_buf;
  426.         ihdr = (INDEX_HDR)  buf->buf_data;
  427.  
  428.         while (blk)
  429.         {       db_get_blk(df, (long) blk, buf);
  430.                 if (db_error) return;
  431.          
  432.  
  433.                 if (!ihdr->idx_rec_cnt)
  434.                 {       db_error = DB_INVALID_INDEX;
  435.                         return;
  436.                 }
  437.  
  438.         idx  = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr)
  439.                    + ihdr->idx_rec_cnt * fh->fh_rec_size);
  440.  
  441.                 blk = idx->idx_idx_ptr;
  442.         }                              
  443.  
  444.     src = buf->buf_data + sizeof(struct db_index_hdr)
  445.         + (ihdr->idx_rec_cnt - 1) * fh->fh_rec_size + fh->fh_ctl_size;
  446.  
  447.     buf->buf_rec_inx = ihdr->idx_rec_cnt;
  448.         memcpy(user_data, src, fh->fh_data_size);
  449. }
  450.  
  451. /*
  452.  *    db_read_prev_idx  -  Read Prev Record in an Index File
  453.  */
  454.  
  455. void db_read_prev_idx(df, user_data)
  456.  DATA_FILE df;
  457.  char *user_data;
  458. {
  459.         FILE_HDR    fh;
  460.         BUFFER     buf;
  461.         INDEX_HDR ihdr;
  462.         INDEX_REC  idx;
  463.         char      *src;
  464.  
  465.                     
  466.         db_error = 0;
  467.  
  468.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  469.         buf  = df->df_buf;
  470.         ihdr = (INDEX_HDR)  buf->buf_data;
  471.                                                
  472.         db_get_blk(df, df->df_prev_blk, buf);
  473.         if (db_error) return;
  474.  
  475.         buf->buf_rec_inx = df->df_prev_rec;
  476.  
  477.         idx = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr)
  478.             + (buf->buf_rec_inx - 1) * fh->fh_rec_size);
  479.  
  480.     if (buf->buf_rec_inx == 1 && idx->idx_idx_ptr == 0)
  481.     {    while (buf->buf_rec_inx == 1)
  482.                 {       db_get_parent_idx(df);
  483.                         if (db_error) return;
  484.                 }
  485.                         
  486.         buf->buf_rec_inx--;
  487.  
  488.                 src = buf->buf_data + sizeof(struct db_index_hdr)
  489.                     + (buf->buf_rec_inx - 1) * fh->fh_rec_size
  490.                     + fh->fh_ctl_size;
  491.  
  492.                 memcpy(user_data, src, fh->fh_data_size);
  493.                 return;
  494.         }
  495.  
  496.         if (idx->idx_idx_ptr)
  497.     {    db_read_last_idx(df, idx->idx_idx_ptr, user_data);
  498.                 return;
  499.         }
  500.  
  501.     buf->buf_rec_inx--;
  502.  
  503.         idx = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr)
  504.             + (buf->buf_rec_inx - 1) * fh->fh_rec_size);
  505.  
  506.         src = ((char *) idx) + fh->fh_ctl_size;
  507.         memcpy(user_data, src, fh->fh_data_size);
  508. }
  509.  
  510.  
  511. /*
  512.  *      db_get_parent_idx  -  Get Parent Block
  513.  */
  514.  
  515. void db_get_parent_idx(df)
  516.  DATA_FILE df;        
  517. {
  518.         FILE_HDR     fh;
  519.         BUFFER      buf;
  520.         INDEX_HDR  ihdr;
  521.         INDEX_REC   idx;
  522.         char      *rbuf;
  523.         ushort hold_blk;
  524.         int         rec;
  525.  
  526.                     
  527.         db_error = 0;
  528.  
  529.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  530.         buf  = df->df_buf;
  531.         rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  532.         ihdr = (INDEX_HDR)  buf->buf_data;                 
  533.  
  534.         hold_blk = buf->buf_cur_blk;
  535.         if (!ihdr->idx_parent)
  536.         {       db_error = DB_END_OF_FILE;
  537.                 return;
  538.         }
  539.  
  540.         db_get_blk(df, (long)ihdr->idx_parent, buf);
  541.         if (db_error) return;
  542.  
  543.         for (rec=1; rec <= ihdr->idx_rec_cnt + 1; rec++)
  544.         {       idx = (INDEX_REC) rbuf;
  545.  
  546.                 if (idx->idx_idx_ptr == hold_blk)
  547.                         break;
  548.  
  549.                 rbuf += fh->fh_rec_size;
  550.         }
  551.  
  552.         if (idx->idx_idx_ptr != hold_blk)
  553.         {       db_error = DB_INVALID_INDEX;
  554.                 return;
  555.         }
  556.  
  557.         buf->buf_rec_inx = rec;
  558. }
  559.  
  560. /*
  561.  *      db_find_first_idx  -  Find First Record
  562.  */
  563.  
  564. void db_find_first_idx(df, user_data, key, key_size)
  565.  DATA_FILE df;
  566.  char *user_data;
  567.  char *key;
  568.  int   key_size;
  569. {
  570.         FILE_HDR  fh;
  571.         BUFFER   buf;
  572.         char   *rbuf;
  573.  
  574.         db_error = 0;
  575.  
  576.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  577.         buf  = df->df_buf;
  578.  
  579.         db_find_insert_idx(df, key, key_size);
  580.         if (db_error) return;
  581.  
  582.         if (!db_match_blk)
  583.         {       db_error = DB_REC_NOT_FOUND;
  584.                 return;
  585.         }
  586.  
  587.         db_get_blk(df, db_match_blk, buf);
  588.         if (db_error) return;
  589.  
  590.         buf->buf_rec_inx = db_match_rec;
  591.  
  592.         rbuf = buf->buf_data + sizeof(struct db_index_hdr)
  593.              + (buf->buf_rec_inx - 1) * fh->fh_rec_size + fh->fh_ctl_size;
  594.  
  595.         memcpy(user_data, rbuf, fh->fh_data_size);
  596. }
  597.  
  598. /*
  599.  *      db_delete_idx  -  Delete an Index Record
  600.  */
  601.  
  602. void db_delete_idx(df)
  603.  DATA_FILE df;
  604. {
  605.         FILE_HDR     fh;
  606.         BUFFER      buf;
  607.         INDEX_HDR  ihdr;
  608.         char       *src, *dst;
  609.         int         cnt, move_flag;
  610.  
  611.         db_error = 0;
  612.  
  613.         move_flag = db_move_to_leaf_idx(df);
  614.         if (db_error) return;       
  615.  
  616.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  617.         buf  = df->df_buf;
  618.         ihdr = (INDEX_HDR) buf->buf_data;
  619.  
  620.         dst = buf->buf_data + sizeof(struct db_index_hdr)
  621.                             + (buf->buf_rec_inx - 1) * fh->fh_rec_size;
  622.         src = dst + fh->fh_rec_size;
  623.         cnt = (ihdr->idx_rec_cnt - buf->buf_rec_inx + 1) * fh->fh_rec_size;
  624.  
  625.         if (cnt) memcpy(dst, src, cnt);
  626.  
  627.         df->df_prev_blk = buf->buf_cur_blk;
  628.         df->df_prev_rec = buf->buf_rec_inx - 1;
  629.  
  630.         ihdr->idx_rec_cnt--;
  631.         if (fh->fh_rec_cnt) fh->fh_rec_cnt--;
  632.  
  633.         if (buf->buf_cur_blk == fh->fh_root_ptr  &&  ihdr->idx_rec_cnt == 0)
  634.         {       fh->fh_root_ptr = 0;
  635.                 db_free_rec(df, buf);
  636.                 if (db_error) return;
  637.         }
  638.         else
  639.         {       db_balance_idx(df);
  640.                 if (db_error) return;
  641.         }
  642.  
  643.         db_put_blk(df, df->df_fhdr);
  644.  
  645.         if (move_flag)
  646.                 db_read_next(df, df->df_tmp->buf_data);
  647. }
  648.  
  649. /*
  650.  *      db_move_to_leaf_idx  -  Move index record to a leaf node 
  651.  *                              before deleting it
  652.  */
  653.  
  654. short db_move_to_leaf_idx(df)
  655.  DATA_FILE df;
  656. {
  657.         FILE_HDR     fh;
  658.         BUFFER      buf, tmp;
  659.         INDEX_HDR  ihdr, thdr;
  660.         INDEX_REC   idx, tdx;
  661.         ulong       blk;
  662.  
  663.         db_error = 0;
  664.  
  665.         fh  = (FILE_HDR) df->df_fhdr->buf_data;
  666.         buf = df->df_buf;
  667.  
  668.         tdx = (INDEX_REC)(buf->buf_data + sizeof(struct db_index_hdr)
  669.                                 + (buf->buf_rec_inx - 1) * fh->fh_rec_size);
  670.  
  671.         if (!tdx->idx_idx_ptr) return(0);
  672.  
  673.         tmp        = df->df_buf;
  674.         buf        = df->df_tmp;
  675.         df->df_buf = buf;
  676.         df->df_tmp = tmp;
  677.                    
  678.         ihdr = (INDEX_HDR) buf->buf_data;
  679.         thdr = (INDEX_HDR) tmp->buf_data;
  680.  
  681.         blk = tdx->idx_idx_ptr;
  682.  
  683.         while (blk)
  684.         {       db_get_blk(df, blk, buf);
  685.                 if (db_error) return(0);
  686.  
  687.                 idx = (INDEX_REC)(buf->buf_data + sizeof(struct db_index_hdr)
  688.                                        + ihdr->idx_rec_cnt * fh->fh_rec_size);
  689.  
  690.                 blk = idx->idx_idx_ptr;
  691.         }
  692.  
  693.         idx = (INDEX_REC)((char *) idx - fh->fh_rec_size);
  694.  
  695.         idx->idx_idx_ptr = tdx->idx_idx_ptr;
  696.         memcpy(tdx, idx, fh->fh_rec_size);
  697.         idx->idx_idx_ptr = 0;
  698.  
  699.         db_put_blk(df, tmp);
  700.         if (db_error) return(0);
  701.  
  702.         buf->buf_rec_inx = ihdr->idx_rec_cnt;
  703.  
  704.         return(1);
  705. }
  706.  
  707. /*
  708.  *      db_balance_idx  -  Rebalance tree after a delete
  709.  */
  710.  
  711. void db_balance_idx(df)
  712.  DATA_FILE df;
  713. {
  714.         FILE_HDR    fh;
  715.         BUFFER     buf,  tmp,  aux;
  716.         INDEX_HDR ihdr, thdr, ahdr;
  717.         INDEX_REC  idx,  tdx,  adx;
  718.         int    min_cnt, hold,  cnt,  op;
  719.         char      *src, *dst;  
  720.  
  721.         db_error = 0;
  722.  
  723.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  724.         buf  = df->df_buf;
  725.         ihdr = (INDEX_HDR) buf->buf_data;
  726.  
  727.         if (buf->buf_cur_blk == fh->fh_root_ptr)
  728.         {       db_put_blk(df, buf);
  729.                 return;
  730.         }
  731.  
  732.         min_cnt = (fh->fh_recs_per_blk + 1) / 2;
  733.         if (ihdr->idx_rec_cnt >= min_cnt)
  734.         {       db_put_blk(df, buf);
  735.                 return;
  736.         }
  737.  
  738.         tmp        = df->df_buf;
  739.         buf        = df->df_tmp;
  740.         df->df_buf = buf;
  741.         df->df_tmp = tmp;
  742.         aux        = df->df_aux;
  743.  
  744.         thdr = (INDEX_HDR) tmp->buf_data;
  745.         ahdr = (INDEX_HDR) aux->buf_data;
  746.         ihdr = (INDEX_HDR) buf->buf_data;
  747.  
  748.         buf->buf_cur_blk = tmp->buf_cur_blk;
  749.         buf->buf_rec_inx = tmp->buf_rec_inx;
  750.         ihdr->idx_parent = thdr->idx_parent;
  751.  
  752.         db_get_parent_idx(df);
  753.         if (db_error) return;
  754.  
  755.         idx  = (INDEX_REC)(buf->buf_data + sizeof(struct db_index_hdr)
  756.                                 + (buf->buf_rec_inx - 1) * fh->fh_rec_size);
  757.  
  758.         if (buf->buf_rec_inx == 1)
  759.         {       adx = (INDEX_REC) ((char *) idx + fh->fh_rec_size);
  760.                 op  = 1;
  761.         }
  762.         else
  763.         {       idx = adx = (INDEX_REC) ((char *) idx - fh->fh_rec_size);
  764.                 buf->buf_rec_inx--;
  765.                 op  = 2;          
  766.         }                              
  767.  
  768.         db_get_blk(df, (long)adx->idx_idx_ptr, aux);
  769.         if (db_error) return;
  770.  
  771.         if (ahdr->idx_rec_cnt <= min_cnt) op += 2;
  772.  
  773.         switch (op)
  774.         {   case 1: /* Rotate Left */
  775.                 if (df->df_prev_blk == aux->buf_cur_blk &&
  776.                     df->df_prev_rec == 0)
  777.                 {       df->df_prev_blk = buf->buf_cur_blk;
  778.                         df->df_prev_rec = buf->buf_rec_inx;
  779.                 }
  780.  
  781.                 if (df->df_prev_blk == buf->buf_cur_blk &&
  782.                     df->df_prev_rec == buf->buf_rec_inx)
  783.                 {       df->df_prev_blk = tmp->buf_cur_blk;
  784.                         df->df_prev_rec = thdr->idx_rec_cnt + 1;
  785.                 }                       
  786.                 else
  787.                 if (df->df_prev_blk == aux->buf_cur_blk &&
  788.                     df->df_prev_rec == 1)
  789.                 {       df->df_prev_blk = buf->buf_cur_blk;
  790.                         df->df_prev_rec = buf->buf_rec_inx;
  791.                 }
  792.                 else
  793.                 if (df->df_prev_blk == aux->buf_cur_blk)
  794.                         df->df_prev_rec--;
  795.  
  796.                 tdx = (INDEX_REC)(tmp->buf_data + sizeof(struct db_index_hdr)
  797.                             + thdr->idx_rec_cnt * fh->fh_rec_size);
  798.                 adx = (INDEX_REC)(aux->buf_data + sizeof(struct db_index_hdr));
  799.  
  800.                 hold = tdx->idx_idx_ptr;
  801.                 memcpy(tdx, idx, fh->fh_rec_size);
  802.                 tdx->idx_idx_ptr = hold;
  803.                 tdx = (INDEX_REC) ((char *) tdx + fh->fh_rec_size);
  804.                 tdx->idx_idx_ptr = adx->idx_idx_ptr;
  805.                 thdr->idx_rec_cnt++;
  806.                 db_put_blk(df,tmp);
  807.                 if (db_error) return;
  808.  
  809.                 if (tdx->idx_idx_ptr)
  810.                 {       hold = tmp->buf_cur_blk;
  811.                         db_get_blk(df, (long)tdx->idx_idx_ptr, tmp);
  812.                         if (db_error) return;
  813.  
  814.                         thdr->idx_parent = hold;
  815.                         db_put_blk(df, tmp);
  816.                         if (db_error) return;
  817.                 }
  818.  
  819.                 hold = idx->idx_idx_ptr;
  820.                 memcpy(idx, adx, fh->fh_rec_size);
  821.                 idx->idx_idx_ptr = hold;
  822.                 db_put_blk(df, buf);
  823.                 if (db_error) return;
  824.  
  825.                 src = (char*) adx + fh->fh_rec_size;
  826.                 cnt = ahdr->idx_rec_cnt * fh->fh_rec_size;
  827.                 memcpy(adx, src, cnt);
  828.                 ahdr->idx_rec_cnt--;
  829.                 db_put_blk(df, aux);
  830.                 if (db_error) return;
  831.                 return;
  832.  
  833.             case 2: /* Rotate Right */ 
  834.                 if (df->df_prev_blk == buf->buf_cur_blk &&
  835.                     df->df_prev_rec == buf->buf_rec_inx)
  836.                 {       df->df_prev_blk = tmp->buf_cur_blk;
  837.                         df->df_prev_rec = 1;
  838.                 }                       
  839.                 else
  840.                 if (df->df_prev_blk == aux->buf_cur_blk &&
  841.                     df->df_prev_rec == ahdr->idx_rec_cnt)
  842.                 {       df->df_prev_blk = buf->buf_cur_blk;
  843.                         df->df_prev_rec = buf->buf_rec_inx;
  844.                 }
  845.                 else
  846.                 if (df->df_prev_blk == tmp->buf_cur_blk)
  847.                         df->df_prev_rec++;
  848.  
  849.                 tdx = (INDEX_REC)(tmp->buf_data + sizeof(struct db_index_hdr));
  850.                 adx = (INDEX_REC)(aux->buf_data + sizeof(struct db_index_hdr)
  851.                                        + ahdr->idx_rec_cnt * fh->fh_rec_size);
  852.  
  853.                 dst = (char *) tdx + fh->fh_rec_size;
  854.                 cnt = (thdr->idx_rec_cnt + 1) * fh->fh_rec_size;
  855.                 memcpy(dst, tdx, cnt);
  856.                 memcpy(tdx, idx, fh->fh_rec_size);
  857.                 tdx->idx_idx_ptr = adx->idx_idx_ptr;
  858.                 thdr->idx_rec_cnt++;
  859.                 db_put_blk(df, tmp);
  860.                 if (db_error) return;
  861.  
  862.                 if (tdx->idx_idx_ptr)
  863.                 {       hold = tmp->buf_cur_blk;
  864.                         db_get_blk(df, (long)tdx->idx_idx_ptr, tmp);
  865.                         if (db_error) return;
  866.  
  867.                         thdr->idx_parent = hold;
  868.                         db_put_blk(df, tmp);
  869.                         if (db_error) return;
  870.                 }
  871.  
  872.                 hold = idx->idx_idx_ptr;
  873.                 adx  = (INDEX_REC) ((char *) adx - fh->fh_rec_size);
  874.                 memcpy(idx, adx, fh->fh_rec_size);
  875.                 idx->idx_idx_ptr = hold;
  876.                 db_put_blk(df, buf);
  877.                 if (db_error) return;
  878.  
  879.                 ahdr->idx_rec_cnt--;
  880.                 db_put_blk(df, aux);
  881.                 if (db_error) return;
  882.                 return;
  883.  
  884.             case 4: /* Merge Right */
  885.                 tmp        = df->df_aux;
  886.                 aux        = df->df_tmp;
  887.                 df->df_aux = aux;
  888.                 df->df_tmp = tmp;
  889.                 thdr       = (INDEX_HDR) tmp->buf_data;
  890.                 ahdr       = (INDEX_HDR) aux->buf_data;
  891.  
  892.             case 3: /* Merge Left */      
  893.                 if (df->df_prev_blk == buf->buf_cur_blk &&
  894.                     df->df_prev_rec == buf->buf_rec_inx)
  895.                 {       df->df_prev_blk = tmp->buf_cur_blk;
  896.                         df->df_prev_rec = thdr->idx_rec_cnt + 1;
  897.                 }                       
  898.                 else
  899.                 if (df->df_prev_blk == aux->buf_cur_blk)
  900.                 {       df->df_prev_blk  = tmp->buf_cur_blk;
  901.                         df->df_prev_rec += thdr->idx_rec_cnt + 1;
  902.                 }                       
  903.  
  904.                 tdx = (INDEX_REC)(tmp->buf_data + sizeof(struct db_index_hdr)
  905.                             + thdr->idx_rec_cnt * fh->fh_rec_size);
  906.                 adx = (INDEX_REC)(aux->buf_data + sizeof(struct db_index_hdr));
  907.  
  908.                 hold = tdx->idx_idx_ptr;
  909.                 memcpy(tdx, idx, fh->fh_rec_size);
  910.                 tdx->idx_idx_ptr = hold;
  911.                 tdx = (INDEX_REC) ((char *) tdx + fh->fh_rec_size);
  912.                 thdr->idx_rec_cnt++;
  913.  
  914.                 cnt = ahdr->idx_rec_cnt * fh->fh_rec_size + fh->fh_ctl_size;
  915.                 memcpy(tdx, adx, cnt);
  916.                 thdr->idx_rec_cnt += ahdr->idx_rec_cnt;
  917.  
  918.                 src = (char *) idx + fh->fh_rec_size;
  919.                 cnt = (ihdr->idx_rec_cnt - buf->buf_rec_inx)
  920.                                        * fh->fh_rec_size + fh->fh_ctl_size;
  921.                 memcpy(idx, src, cnt);
  922.                 idx->idx_idx_ptr = tmp->buf_cur_blk;
  923.                 ihdr->idx_rec_cnt--;
  924.  
  925.                 src = buf->buf_data + sizeof(struct db_index_hdr)
  926.                     + ihdr->idx_rec_cnt * fh->fh_rec_size + fh->fh_ctl_size;
  927.                 cnt = fh->fh_rec_size;
  928.                 memset(src, 0, cnt);
  929.  
  930.         if (buf->buf_cur_blk == fh->fh_root_ptr)
  931.                     if (!ihdr->idx_rec_cnt)
  932.                             thdr->idx_parent = 0;
  933.  
  934.                 db_put_blk(df, tmp);
  935.                 if (db_error) return;
  936.  
  937.                 hold = ahdr->idx_rec_cnt + 1;
  938.                 db_free_rec(df, aux);
  939.                 if (db_error) return;
  940.  
  941.                 for (cnt=1; cnt <= hold; cnt++)
  942.                 {       if (tdx->idx_idx_ptr)
  943.                         {       db_get_blk(df, (long)tdx->idx_idx_ptr, aux);
  944.                                 if (db_error) return;
  945.  
  946.                                 ahdr->idx_parent = tmp->buf_cur_blk;
  947.                                 db_put_blk(df, aux);
  948.                                 if (db_error) return;
  949.                         }
  950.                         tdx = (INDEX_REC)((char *) tdx + fh->fh_rec_size);
  951.                 }
  952.  
  953.                 if (buf->buf_cur_blk == fh->fh_root_ptr)
  954.                 {       if (!ihdr->idx_rec_cnt)
  955.                         {       fh->fh_root_ptr = tmp->buf_cur_blk;
  956.                                 db_free_rec(df, buf);
  957.                                 if (db_error) return;
  958.                         }
  959.                         else
  960.                         {       db_put_blk(df, buf);
  961.                                 if (db_error) return;
  962.                         }
  963.                 }
  964.                 else
  965.                 {       db_balance_idx(df);
  966.                         if (db_error) return;
  967.                 }
  968.  
  969.                 return;
  970.         }
  971. }
  972.  
  973. /*
  974.  *      db_update_idx - Update an Index record
  975.  */
  976.  
  977. void db_update_idx(df, user_data)
  978.  DATA_FILE  df;
  979.  char     *user_data;
  980. {
  981.         INDEX_HDR   ihdr;
  982.         FILE_HDR    fh;
  983.         BUFFER      buf;
  984.         char       *rbuf;
  985.  
  986.         db_error = 0;
  987.  
  988.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  989.         buf  = df->df_buf;
  990.         ihdr = (INDEX_HDR) buf->buf_data;
  991.  
  992.         if (ihdr->idx_rec_cnt < buf->buf_rec_inx)
  993.         {       db_error = DB_DELETED_REC;
  994.                 return;
  995.         }
  996.  
  997.         rbuf = buf->buf_data + sizeof(struct db_index_hdr)
  998.              + (buf->buf_rec_inx - 1) * fh->fh_rec_size;
  999.  
  1000.         memcpy(rbuf+fh->fh_ctl_size, user_data, fh->fh_data_size);
  1001.         db_put_blk(df, buf);
  1002.         return;
  1003. }
  1004.